package algorithm.easy;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Solution {
    /*1. 两数之和
         给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
         输入：nums = [2,7,11,15], target = 9
         输出：[0,1]
    */
    public static int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }
    //1. 两数之和版本2
    public static int[] twoSum2(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],i);
        }
        for(int i=0;i<nums.length;i++){
            Integer temp = target - nums[i];
            if(map.containsKey(temp) && map.get(temp)!=i){
                return new int[]{i,map.get(temp)};
            }
        }
        return null;
    }
    //1. 两数之和版本3
    public static int[] twoSum3(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(!map.containsKey(nums[i])){
                //将结果存起来，再在后续遍历过程中找对应的结果值
                map.put(target-nums[i],i);
            }else{
                return new int[]{map.get(nums[i]),i};
            }
        }
        return null;
    }

    //9. 回文数
    //输入:x = 121

    public static boolean isPalindrome(int x) {
        int revertedNumber = 0;
        if(x<0){
            return false;
        }else{
            /*
            int p = x;
            int remainder = 0;
            int revertedNumber = 0;
            do{
                remainder = p % 10;
                revertedNumber = revertedNumber*10 + remainder;
                x = x /10;
            }while(x > 0);
             if(p == revertedNumber){
                return true;
            }
            */
            //折半查找，防止数据溢出
            while(x > revertedNumber){
                revertedNumber =revertedNumber*10 + x % 10;
                x = x/10;
            }
        }
        return x == revertedNumber|| x== revertedNumber /10;//折半查找
        //return false; //do-while
    }
    //9. 回文数2
    //输入:x = 121
    public static boolean isPalindrome2(int x) {
        if(x<0 || (x%10==0&&x!=0)){
            return false;
        }
        char[] cs = String.valueOf(x).toCharArray();
        for(int i=0;i<cs.length;i++){
            if(cs[i] != cs[cs.length-i-1]){
                return false;
            }
        }
       return true;
    }

    //13 罗马数字转整数
    /*
    //字符          数值
        //I             1
        //V             5
        //X             10
        //L             50
        //C             100
        //D             500
        //M             1000
        // I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
        // X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
        // C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

        //输入: s = "MCMXCIV"
        //输出: 1994
        //解释: M = 1000, CM = 900, XC = 90, IV = 4.
     */
    public static int romanToInt(String s) {
        int sum = 0;
        /*
        Map<String,Integer> RToISim = new HashMap<>();
        Map<String,Integer> RToCom = new HashMap<>();
        RToISim.put("I",1); RToISim.put("V",5); RToISim.put("X",10);
        RToISim.put("L",50);RToISim.put("C",100);RToISim.put("D",500);
        RToISim.put("M",1000);

        RToCom.put("IV",4);RToCom.put("IX",9);
        RToCom.put("XL",40);RToCom.put("XC",90);
        RToCom.put("CD",400);RToCom.put("CM",900);
        String sr = s;

        //先处理特殊情况
        for(Map.Entry<String,Integer> entry : RToCom.entrySet()){
            if(sr.contains(entry.getKey())){
                sr = sr.replace(entry.getKey(),"");
                sum += entry.getValue();
            }
        }
        char[] ch = sr.toCharArray();
        for(int i=0;i<ch.length;i++){
            sum += RToISim.get(new String().valueOf(ch[i]));
        }
        */
        //I-1,V-5,X-10,L-50,C-100,D-500,M-1000,IV-4,IX-9,XL-40,XC-90,CD-400,CM-900。
        char[] ch = s.toCharArray();
        for(int i=0;i < ch.length;i++){
            switch(ch[i]){
                case 'I':sum += 1;
                    break;
                case 'V':
                    if(i>0 && ch[i-1]=='I'){
                        sum += 3;
                    } else{
                            sum += 5;
                    }
                    break;
                case 'X':
                    if(i>0 && ch[i-1]=='I'){
                        sum += 8;
                    } else{
                        sum += 10;
                    }
                    break;
                case 'L':
                    if(i>0 && ch[i-1]=='X'){
                        sum += 30;
                    } else{
                        sum += 50;
                    }
                     break;
                case 'C':
                    if(i>0 && ch[i-1]=='X'){
                        sum += 80;
                    } else{
                        sum += 100;
                    }
                    break;
                case 'D':
                    if(i>0 && ch[i-1]=='C'){
                        sum += 300;
                    } else{
                        sum += 500;
                    }
                    break;
                case 'M':
                    if(i>0 && ch[i-1]=='C'){
                        sum += 800;
                    } else{
                        sum += 1000;
                    }
                    break;
            }
        }

        return sum;
    }

    /*
    //14 最长公共前缀
    //输入：s = "()[]{}"
    //输出：true
     */
    public static String longestCommonPrefix(String[] strs) {
        //还可以继续优化 - 用while循环+String.startWith试试
        String rs = "";
        if(strs==null){
            return rs ;
        }
        rs = strs[0];
        for(int i=1;i<strs.length;i++){
            String rs1 = rs;
            if(i==1){
                rs1 = strs[i-1];
            }
            String rs2 = strs[i];
            char[] c1 = rs1.toCharArray();
            char[] c2 = rs2.toCharArray();
            int p=0;
            for(;p<c1.length;p++){
                if(p<c2.length && c1[p]==c2[p]){
                    p++;
                }else{
                    rs = rs1.substring(0,p);
                    break;
                }
            }
        }
        return rs;
    }
    /*
        // 20  有效的括号-建议用栈实现
        //输入：s = "()[]{}"
        //输出：true
     */
    public static boolean isValid(String s) {
        Map<Character,Character> map = new HashMap<Character,Character>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');
        Stack<Character> stack = new Stack<>();

        for(int i=0;i<s.length();i++){
            Character ch = new Character(s.charAt(i));

            if(map.containsKey(ch)){
                stack.push(ch);
            }else{
                Character chr = stack.pop();
                System.out.println("出栈'"+chr+"'匹配'"+ch+"'");
                Character value = map.get(chr);
                if(value.charValue()!=(ch.charValue())){
                    return false;
                }
                /*if(ch==')' && chr!='('){
                   return false;
                }
                if(ch==')' && chr!='('){
                    return false;
                }
                if(ch==')' && chr!='('){
                    return false;
                }*/
            }
        }
        if(stack.size()>0){
            return false;
        }
        return true;
    }


    public static void main(String[] args){
        //eg:1
        //int[] nums = {2,7,11,15};int target = 17;
        //System.out.print(Arrays.toString(twoSum3(nums,target)));
        //eg:9
        //int x = 1213121;
        //System.out.println(isPalindrome2(x));
        //eg:13
        //String  s = "MCMXCIV";
        //System.out.println(romanToInt(s));
        //String[] strs = new String[]{"flower","flow","flight"};
        //System.out.println(longestCommonPrefix(strs));
        //eg:14
        // String strs =  "([]{})";
        // System.out.println(isValid(strs));


    }
}
